package cn.edu.xjtu.work.rotate;

import java.util.Arrays;

/**
 * 旋转数组
 * 
 * 给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
 */
public class Soluition {
  public static void main(String[] args) {
    // int[] nums = new int[] { 1, 2, 3, 4, 5, 6, 7 };
    int[] nums = new int[] { -1, -100, 3, 99 };
    // rotate1(nums, 2);
    rotate2(nums, 2);
    System.out.println(Arrays.toString(nums));
  }

  /**
   * 
   * @param nums
   * @param k
   */
  public static void rotate2(int[] nums, int k) {
    if (nums.length == 0) {
      return;
    }
    int hold = nums[0];
    int index = 0;
    int[] visited = new int[nums.length];
    for (int i = 0; i < nums.length; i++) {
      index = (index + k) % nums.length;
      if (visited[index] == 1) {
        // 如果访问过的话查找该元素的下一个元素是否来过
        index = (index + 1) % nums.length;
        hold = nums[index];
        i--;
      } else {
        // 如果没访问过的话将保存的值与当前元素的值进行交换,同时设置访问状态
        int temp = nums[index];
        nums[index] = hold;
        hold = temp;
        visited[index] = 1;
      }

    }
  }

  /**
   * 向右移动k位,即向左移动nums.length-k位,构造几个新数组存储结果,最后将结果传递给传入的数组
   * 
   * @param nums
   * @param k
   */
  public static void rotate1(int[] nums, int k) {
    if (k > nums.length) {
      // 当k比nums.length大时,进行取余,不然会出现nums.length-k位负数从而数组越界
      k = k % nums.length;
    }
    if (k == nums.length) {
      return;
    }
    int[] arr = new int[nums.length];
    for (int i = 0; i < nums.length; i++) {
      arr[i] = nums[(i + nums.length - k) % nums.length];
    }
    for (int i = 0; i < arr.length; i++) {
      nums[i] = arr[i];
    }
  }

}
